package com.lwg.datastructure.dynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author: lwg
 * @Date: 2022/2/18 21:54
 * @Description: 删除并获得点数
 */

/*
    和打家劫舍类似 只不过加了一层 我们需要转化一下
    因为当我们选择x时 则x-1 和x+1 都不能选了 但是相同的数我们是可以选的，我们只需要
    得到每个数的总和来进行判断大小即可
    1. 我们可以利用最大数来作为新数组的空间大小，这样就不会超出索引
    2. 比如说[2,2,3,3,3,4]  =>  [0,0,4,9,4]  即将前一个数组的大小值作为新数组的下标
       而每个数的和作为对应下标的值，例如新数组  sum[2]=4,sum[3]=9,sum[4]=4
    3. 此时我们利用打家劫舍的公式 dp[i]=Math.max(dp[i-2]+sum[i],dp[i-1])来计算
       也可以利用滚动数字的方式进行,这样就可以将所有的数保存到dp数组中而转换成了只保存前后两个数中的情况
       即  first=sum[0]; int second=Math.max(first,sum[1]); int temp=second; second=Math.max(first+sum[i],second);  first=temp;
       注意：为什么转换成这样就可以利用这个公式呢=?(原先不是相邻的不能偷吗)
       因为数字相邻的 即x-1和x+1 的我们已经把它转换成了相对应的下标 索引也就变成了新数组中不能选择相邻的房屋进行偷窃了
 */

public class Plunder3 {

    public int deleteAndEarn(int[] nums) {
        // 1. 得到数组的长度
        int length = nums.length;
        // 2. 遍历得到最大的数，作为新数组的空间大小
        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }
        int sum[] = new int[maxNum + 1];
        // 3. 将与下标相同的数保存到对应的数组中去
        for (int num : nums) {
            sum[num] += num;
        }
        return rob(sum);
    }

    public int rob(int[] sum) {
        int first = sum[0];
        int second = Math.max(first, sum[1]);
        // 4. 打家劫舍公式
        for (int i = 2; i < sum.length; i++) {
            int temp = second;
            second = Math.max(first + sum[i], second);
            first = temp;
        }
        return second;
    }
}

class MainClass10 {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int[] nums = stringToIntegerArray(line);

            int ret = new Plunder3().deleteAndEarn(nums);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}
